<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>

<script>
    function diff(oldVnode, newVnode) {
        // 如果旧节点不存在，则创建新节点
        if (!oldVnode) {
            createElm(newVnode);
        } else if (sameVnode(oldVnode, newVnode)) {
            // 如果新旧节点是相同的，则进行patch操作
            patchVnode(oldVnode, newVnode);
        } else {
            // 如果新旧节点不同，则创建新节点并替换旧节点
            const oldElm = oldVnode.elm;
            const parentElm = oldElm.parentNode;
            createElm(newVnode);
            parentElm.insertBefore(newVnode.elm, oldElm);
            parentElm.removeChild(oldElm);
        }
    }


    function createElm(vnode) {
        const { tag, data, children, text } = vnode;
        //虚拟DOM节点的标签名
        if (tag) {
            // 创建元素节点
            vnode.elm = document.createElement(tag);
            // 虚拟DOM节点的属性和事件等其他数据
            if (data) {
                for (let key in data) {
                    vnode.elm.setAttribute(key, data[key]);
                }
            }
            // 虚拟DOM节点的子节点
            if (children) {
                children.forEach(child => {
                    createElm(child);
                    vnode.elm.appendChild(child.elm);
                });
            }
        } else {
            // 创建文本节点
            vnode.elm = document.createTextNode(text);
        }
    }

    function patchVnode(oldVnode, newVnode) {
        const elm = newVnode.elm = oldVnode.elm;
        const oldCh = oldVnode.children;
        const newCh = newVnode.children;

        // 如果新旧节点相同，则直接返回
        if (oldVnode === newVnode) {
            return;
        }

        // 如果新节点有文本内容，则更新元素的文本内容
        if (newVnode.text) {
            if (newVnode.text !== oldVnode.text) {
                elm.textContent = newVnode.text;
            }
        } else {
            // 如果新节点没有文本内容，则比较子节点
            if (oldCh && newCh && oldCh !== newCh) {
                updateChildren(elm, oldCh, newCh);
            } else if (newCh) {
                // 如果新节点有子节点而旧节点没有，则创建新节点的子节点
                createElm(newVnode);
                newCh.forEach(child => {
                    newVnode.elm.appendChild(child.elm);
                });
            } else if (oldCh) {
                // 如果旧节点有子节点而新节点没有，则删除旧节点的子节点
                elm.textContent = '';
            }
        }
    }

    function updateChildren(parentElm, oldCh, newCh) {
        //旧节点开始的位置
        let oldStartIdx = 0;
        let oldEndIdx = oldCh.length - 1;
        let newStartIdx = 0;
        let newEndIdx = newCh.length - 1;
        let oldStartVnode = oldCh[oldStartIdx];
        let oldEndVnode = oldCh[oldEndIdx];
        let newStartVnode = newCh[newStartIdx];
        let newEndVnode = newCh[newEndIdx];

        while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            // 如果旧节点的开始节点不存在，则指向下一个节点
            if (!oldStartVnode) {
                oldStartVnode = oldCh[++oldStartIdx];
            }
            // 如果旧节点的结束节点不存在，则指向上一个节点
            else if (!oldEndVnode) {
                oldEndVnode = oldCh[--oldEndIdx];
            }
            // 如果新节点的开始节点不存在，则指向下一个节点
            else if (!newStartVnode) {
                newStartVnode = newCh[++newStartIdx];
            }
            // 如果新节点的结束节点不存在，则指向上一个节点
            else if (!newEndVnode) {
                newEndVnode = newCh[--newEndIdx];
            }
            // 如果旧节点的开始节点和新节点的开始节点相同，则进行patch操作
            else if (sameVnode(oldStartVnode, newStartVnode)) {
                patchVnode(oldStartVnode, newStartVnode);
                oldStartVnode = oldCh[++oldStartIdx];
                newStartVnode = newCh[++newStartIdx];
            }
            // 如果旧节点的结束节点和新节点的结束节点相同，则进行patch操作
            else if (sameVnode(oldEndVnode, newEndVnode)) {
                patchVnode(oldEndVnode, newEndVnode);
                oldEndVnode = oldCh[--oldEndIdx];
                newEndVnode = newCh[--newEndIdx];
            }
            // 如果旧节点的开始节点和新节点的结束节点相同，则进行patch操作
            else if (sameVnode(oldStartVnode, newEndVnode)) {
                patchVnode(oldStartVnode, newEndVnode);
                parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
                oldStartVnode = oldCh[++oldStartIdx];
                newEndVnode = newCh[--newEndIdx];
            }
            // 如果旧节点的结束节点和新节点的开始节点相同，则进行patch操作
            else if (sameVnode(oldEndVnode, newStartVnode)) {
                patchVnode(oldEndVnode, newStartVnode);
                parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
                oldEndVnode = oldCh[--oldEndIdx];
                newStartVnode = newCh[++newStartIdx];
            }
            // 如果以上条件都不满足，则通过key值比较节点
            else {


                const keyToIndex = createKeyToIndex(oldCh, oldStartIdx, oldEndIdx);
                console.log(keyToIndex, 'lllllllllllllllllll');
                const index = keyToIndex[newStartVnode.key];
                if (index === undefined) {
                    // 如果新节点的key在旧节点中不存在，则创建新节点并插入到旧节点的开始节点之前
                    createElm(newStartVnode);
                    parentElm.insertBefore(newStartVnode.elm, oldStartVnode.elm);
                } else {
                    const vnodeToMove = oldCh[index];
                    if (sameVnode(vnodeToMove, newStartVnode)) {
                        // 如果找到相同的节点，则进行patch操作
                        patchVnode(vnodeToMove, newStartVnode);
                        oldCh[index] = undefined;
                        parentElm.insertBefore(vnodeToMove.elm, oldStartVnode.elm);
                    } else {
                        // 如果找到相同的key但节点不同，则创建新节点并插入到旧节点的开始节点之前
                        createElm(newStartVnode);
                        parentElm.insertBefore(newStartVnode.elm, oldStartVnode.elm);
                    }
                }
                newStartVnode = newCh[++newStartIdx];



            }
        }

        // 如果旧节点的开始索引大于结束索引，则说明旧节点的子节点已经全部处理完毕
        if (oldStartIdx > oldEndIdx) {
            // 如果新节点的开始索引小于等于结束索引，则说明新节点还有剩余未处理的子节点
            if (newStartIdx <= newEndIdx) {
                const before = newCh[newEndIdx + 1] ? newCh[newEndIdx + 1].elm : null;
                for (let i = newStartIdx; i <= newEndIdx; i++) {
                    createElm(newCh[i]);
                    parentElm.insertBefore(newCh[i].elm, before);
                }
            }
        }
        // 如果新节点的开始索引大于结束索引，则说明新节点的子节点已经全部处理完毕
        else if (newStartIdx > newEndIdx) {
            // 如果旧节点的开始索引小于等于结束索引，则说明旧节点还有剩余未处理的子节点
            if (oldStartIdx <= oldEndIdx) {
                for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                    const child = oldCh[i];
                    if (child) {
                        parentElm.removeChild(child.elm);
                    }
                }
            }
        }
    }

    function sameVnode(oldVnode, newVnode) {
        return oldVnode.key === newVnode.key && oldVnode.tag === newVnode.tag;
    }

    function createKeyToIndex(children, beginIdx, endIdx) {
        const map = {};
        for (let i = beginIdx; i <= endIdx; i++) {
            const child = children[i];
            if (child) {
                //将一个旧子节点的key属性和对应的索引值存储到一个映射表中
                //通过map对象，我们可以将旧子节点中的key属性和对应的索引值进行映射
                //这个映射表可以帮助我们在后续的比较中快速查找新子节点中具有相同key属性的节点，并确定它们在旧子节点中的位置
                //这样可以方便地进行虚拟DOM的比较和更新操作，提高性能和效率
                map[child.key] = i;
            }
        }
        return map;
    }

</script>

</html>